package com.yangzhe.algorithm.c035;

import java.util.HashMap;
import java.util.Map;

// 实现LRU结构
public class Code02_LRU_LeetCode {
    public static void main(String[] args) {
        LRUCache cache = new LRUCache(1);
        cache.get(6);
        cache.get(8);
        cache.put(12, 1);
        cache.get(2);
        cache.put(15, 11);
        cache.put(5, 2);
        cache.put(1, 15);
        cache.put(4, 2);
        cache.get(4);
        cache.put(15, 15);

    }


    /**
     * 测试链接 : https://leetcode.cn/problems/lru-cache/
     * 使用双向链表，最新使用过的node放到链表尾部，如果满了则淘汰链表头部
     * 使用Hashmap记录所有链表节点的引用
     */
    static class LRUCache {
        private int capacity = 0;

        public LRUCache(int capacity) {
            this.capacity = capacity;
        }

        public int get(int key) {
            if (!map.containsKey(key)) {
                return -1;
            }

            DoubleLinkedNode node = map.get(key);
            doubleLinkedList.moveToTail(node);

            return node.value;
        }

        public void put(int key, int value) {
            DoubleLinkedNode node;
            // 如果存在则修改node的值
            if (map.containsKey(key)) {
                node = map.get(key);
                node.value = value;

                doubleLinkedList.moveToTail(node);
            } else {
                // 先空出位置
                if (map.size() == this.capacity) {
                    DoubleLinkedNode doubleLinkedNode = doubleLinkedList.removeHead();
                    map.remove(doubleLinkedNode.key);
                }

                // 不存在则添加node
                node = new DoubleLinkedNode();
                node.key = key;
                node.value = value;
                doubleLinkedList.addToTail(node);
            }

            map.put(key, node);

        }


        public Map<Integer, DoubleLinkedNode> map = new HashMap<>();
        public DoubleLinkedList doubleLinkedList = new DoubleLinkedList();

        /**
         * 链表节点
         */
        class DoubleLinkedNode {
            DoubleLinkedNode prev;
            DoubleLinkedNode next;
            int key;
            int value;
        }

        /**
         * 实现双向链表
         */
        class DoubleLinkedList {
            public DoubleLinkedNode head;
            public DoubleLinkedNode tail;

            public void addToTail(DoubleLinkedNode node) {
                if (tail == null) {
                    head = node;
                    tail = node;
                } else {
                    tail.next = node;
                    node.prev = tail;
                    node.next = null;

                    tail = node;
                }
            }

            public void moveToTail(DoubleLinkedNode node) {
                if (node == tail) {
                    return;
                }
                DoubleLinkedNode prevNode = node.prev;
                DoubleLinkedNode nextNode = node.next;
                if (node == head) {
                    head = node.next;
                    head.prev = null;
                }
                if (prevNode != null) {
                    prevNode.next = nextNode;
                }

                if (nextNode != null) {
                    nextNode.prev = prevNode;
                }

                tail.next = node;
                node.prev = tail;
                node.next = null;

                tail = node;
            }

            public DoubleLinkedNode removeHead() {
                DoubleLinkedNode removedNode = null;
                if (head != null) {
                    removedNode = head;
                    DoubleLinkedNode next = head.next;
                    head.next = null;
                    if (next != null) {
                        next.prev = null;
                    } else {
                        // 如果head下个节点为空，则head就是tail
                        tail = null;
                    }
                    head = next;
                }

                return removedNode;
            }
        }
    }


}
